#include <iostream>
#include <queue>

using namespace std;

const int N = 1e5 + 10;
int e[N * 2], ne[N * 2], h[N], id, w[N * 2];
int n, m;
bool st[N]; 

void add(int a, int b, int c)
{
	id++;
	e[id] = b;
	w[id] = c;
	ne[id] = h[a];
	h[a] = id;
}

void dfs(int u)
{
	st[u] = true;
	cout << u << " ";
	for(int i = h[u]; i; i = ne[i])
	{
		int a = e[i], b = w[i];
		if(!st[a])
		{
			dfs(a);
		}
	}
}

void bfs(int u)
{
	queue<int> q;
	q.push(u);
	st[u] = 1;
	while(q.size())
	{
		int v = q.front(); q.pop();
		cout << v << " ";
		for(int i = h[v]; i; i = ne[i])
		{
			int a = e[i], b = w[i];
			if(!st[v])
			{
				q.push(a);
				st[a] = true;
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int a, b, c; cin >> a >> b >> c;
		add(a, b, c); add(b, a, c);
	}
	dfs(1);
	bfs(1);
	return 0;
}
